iT邦幫忙

0

[用 Python 解 LeetCode] (002) 26. Remove Duplicates from Sorted Array

  • 分享至 

  • xImage
  •  

題幹懶人包

基本上跟27題很像,輸入是一個已經排序好的數組,最後輸出非重複數值的數量,然後以下幾點要注意:

  1. 只能修改該數組,利用的空間複雜度最多為1(意思就是不能創建新的數組append值)

  2. 不用管超過回傳值以後nums的值

    """
    比方說輸入的 nums = [0,0,1,1,1,2,2,3,3,4]
    那最後回傳值要等於五,且 nums[:5] 要包含 0, 1, 2, 3, 4 這幾個數字,然後數字在該切片裡的順序不重要
    """
    

while 解法

head 紀錄當前非重複的下標 (有點像 selection sort),i 迴圈遍歷到的當前元素,如果跟當前不一樣非重複下標 head 加一,然後新的下標得值跟不一樣的值進行交換。1

class Solution:
    def removeDuplicates(self, nums) -> int:
        head = 0
        i = 1
        while i < len(nums):
            if nums[head] != nums[i]:
                head += 1
                nums[head], nums[i] = nums[i], nums[head]
            i += 1
        return head + 1

for 解法

跟 while 原理一樣只是改寫 (這裡用for 會好一點,因為不管怎麼樣都要循環整個數組)

class Solution:
    def removeDuplicates(self, nums) -> int:
        head = 0
        for i in range(1, len(nums)):
            if nums[head] != nums[i]:
                head += 1
                nums[head]= nums[i]
        return nums

別人的寫法

意義跟上面一樣,只是從紀錄非重複的,變成紀錄重複的數量

class Solution:
    def removeDuplicates(self, nums) -> int:
        count = 0
        for i in range(1, len(nums)):
            if nums[i] == nums[i-1]:
                count += 1
            else:
                nums[i-count] = nums[i]
        return nums

圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言